// -----------------------------------------------------------------------
// ---- Livro Algoritmos (de Dasgupta, Vazirani, Papadimitriou) ----------
// ---- Problema da DISTANCIA DE EDICÃO (Capítulo 6.2) -------------------
// -----------------------------------------------------------------------
#include <iostream>
using namespace std;


int EditDistance(string X, string Y, char**& op);

void imprime_edit_op(int i, int j, char** R, string X, string Y, string op1, string op2);
void imprime_matriz(string X, string Y, char** R);
void imprime_matriz(string X, string Y, int** R);

// -------------------------------------------------------------
// --- MAIN ----------------------------------------------------
// -------------------------------------------------------------
int main() {
    string X = "SNOWY";
    string Y = "SUNNY";
    //string X = "ALGORITMO";
    //string Y = "SALGADO";
    int m = X.size();
    int n = Y.size();

    cout << "\n---------------------------------------------\n";
    cout << "Entrada X = " << X << "\n";
    cout << "Entrada Y = " << Y << "\n\n";

    char** R = NULL;
    int edit = EditDistance(X,Y,R);
    cout << "Edit Distance = " << edit << "\n\n";


    cout << "\n---------------------------------------------\n";
    cout << "Todas as solucoes otimas:\n\n";
    string op1, op2;
    imprime_edit_op(m,n,R,X,Y,op1,op2);


    cout << "\n---------------------------------------------\n";
    cout << "Matriz de Operacoes de Edicao:\n\n";
    imprime_matriz(X,Y,R);

    cout << "\n\n";
    cout << "LEGENDA:\n";
    cout << "1 (diagonal == substituir)\n";
    cout << "2 (pra esquerda == inserir)\n";
    cout << "3 (pra cima == remover)\n";
    cout << "4 (1 ou 2)\n";
    cout << "5 (1 ou 3)\n";
    cout << "6 (2 ou 3)\n";
    cout << "7 (1 ou 2 ou 3)\n";
    cout << "\n---------------------------------------------\n\n";

    if (R!=NULL) {
        for (int i=0; i<=m; i++) delete[] R[i];
        delete[] R;
    }
    return 0;
}


// --------------------------------------------------------------------
// ---- ALGORITMO EDIT-DISTANCE (distancia de edicao) -----------------
// --------------------------------------------------------------------
int EditDistance(string X, string Y, char**& R) {
    int i,j;
    int m = X.size();
    int n = Y.size();
    int** Ed = new int*[m+1];    for(i=0;i<=m;i++)Ed[i]=new int[n+1];
    if(R==NULL){R=new char*[m+1];for(i=0;i<=m;i++) R[i]=new char[n+1];}

    for (j=0; j<=n; j++) {Ed[0][j] = j;   R[0][j] = '2';}
    for (i=0; i<=m; i++) {Ed[i][0] = i;   R[i][0] = '3';}

    for (i=1; i<=m; i++) {
        for (j=1; j<=n; j++) {
            int dif = 1;
            if (X[i-1]==Y[j-1]) dif = 0;
            int a = Ed[i-1][j-1] + dif;
            int b = Ed[i][j-1] + 1;
            int c = Ed[i-1][j] + 1;
            if ((a<b)&&(a<c)) {
                Ed[i][j] = a;  R[i][j] = '1';
            } else if ((b<a)&&(b<c)) {
                Ed[i][j] = b;  R[i][j] = '2';
            } else if ((c<a)&&(c<b)) {
                Ed[i][j] = c;  R[i][j] = '3';
            } else if ((a==b)&&(a<c)) {
                Ed[i][j] = a;  R[i][j] = '4';
            } else if ((a==c)&&(a<b)) {
                Ed[i][j] = a;  R[i][j] = '5';
            } else if ((b==c)&&(b<a)) {
                Ed[i][j] = b;  R[i][j] = '6';
            } else {//if ((a==b)&&(b==c)) {
                Ed[i][j] = a;  R[i][j] = '7';
            }
        }
    }

    int edit = Ed[m][n];
    cout << "\n---------------------------------------------\n";
    cout << "Matriz de Distancias de Edicao:\n\n";
    imprime_matriz(X,Y,Ed);

    for (i=0; i<=m; i++) delete[] Ed[i];
    delete[] Ed;
    return edit;
}



// -------------------------------------------------------------
// --- AUXILIARES ----------------------------------------------
// -------------------------------------------------------------
void imprime_edit_op(int i, int j, char** R, string X, string Y, string op1, string op2) {
    if ((i==0)&&(j==0)) {
        cout << op1 << "\n";
        cout << op2 << "\n\n";
        return;
    }
    if (R[i][j]=='1') {
        imprime_edit_op(i-1, j-1, R, X, Y, string(1,X[i-1])+op1, string(1,Y[j-1])+op2);
        return;
    } else
    if (R[i][j]=='2') {
        imprime_edit_op(i, j-1, R, X, Y, "_"+op1, string(1,Y[j-1])+op2);
        return;
    } else
    if (R[i][j]=='3') {
        imprime_edit_op(i-1, j, R, X, Y, string(1,X[i-1])+op1, "_"+op2);
        return;
    } else
    if (R[i][j]=='4') {
        imprime_edit_op(i-1, j-1, R, X, Y, string(1,X[i-1])+op1, string(1,Y[j-1])+op2);
        imprime_edit_op(i, j-1, R, X, Y, "_"+op1, string(1,Y[j-1])+op2);
        return;
    } else
    if (R[i][j]=='5') {
        imprime_edit_op(i-1, j-1, R, X, Y, string(1,X[i-1])+op1, string(1,Y[j-1])+op2);
        imprime_edit_op(i-1, j, R, X, Y, string(1,X[i-1])+op1, "_"+op2);
        return;
    } else
    if (R[i][j]=='6') {
        imprime_edit_op(i, j-1, R, X, Y, "_"+op1, string(1,Y[j-1])+op2);
        imprime_edit_op(i-1, j, R, X, Y, string(1,X[i-1])+op1, "_"+op2);
        return;
    } else
    if (R[i][j]=='7') {
        imprime_edit_op(i-1, j-1, R, X, Y, string(1,X[i-1])+op1, string(1,Y[j-1])+op2);
        imprime_edit_op(i, j-1, R, X, Y, "_"+op1, string(1,Y[j-1])+op2);
        imprime_edit_op(i-1, j, R, X, Y, string(1,X[i-1])+op1, "_"+op2);
        return;
    }
}

void imprime_matriz(string X, string Y, char** R) {
    int i,j;
    int m = X.size();
    int n = Y.size();

    cout << "  " << Y << "\n ";
    for (j=0; j<=n; j++) cout << " ";
    cout << "\n";
    for (i=1; i<=m; i++) {
        cout << X[i-1] << " ";
        for (j=1; j<=n; j++) cout << R[i][j];
        cout << "\n";
    }
}

void imprime_matriz(string X, string Y, int** R) {
    int i,j;
    int m = X.size();
    int n = Y.size();

    cout << "   " << Y << "\n  ";
    for (j=0; j<=n; j++) cout << R[0][j];
    cout << "\n";
    for (i=1; i<=m; i++) {
        cout << X[i-1] << " ";
        for (j=0; j<=n; j++) cout << R[i][j];
        cout << "\n";
    }
    cout << "\n\n";
}